#pragma once

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<time.h>

#include<thread>
#include<mutex>
#include<atomic>

#include<assert.h>
using std::cout;
using std::endl;

#ifdef _WIN32
	#include<Windows.h>
#else
	//Linux
#endif

static const size_t MAX_BYTES = 256 * 1024;//threadcache最大256kb
static const size_t NFREELISTS = 208;//使用static const代替define，208是根据定义的字节对齐算出的总共桶数
static const size_t NPAGES = 129;//总共Page桶数，128为最大页数，假设1页有8Kb，128*8Kb=1Mb，完全够给最大字节256Kb分4个
static const size_t PAGE_SHIFT = 13;//2^13 页大小8k

//获取结点obj存的下一个结点地址（前4/8字节）,加static仅当前文件可见，防止重定义
static void*& NextObj(void* obj)
{
	return *((void**)obj);
}

//管理切好的小对象自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	void* Pop( )
	{
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t Size()
	{
		return _size;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;//自由链表最大个数
	size_t _size = 0;
};

//管理对齐和映射等关系
class AMSize
{
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128] 8byte对齐       freelist[0,16)
	// [128+1,1024] 16byte对齐   freelist[16,72)
	// [1024+1,8*1024] 128byte对齐   freelist[72,128)
	// [8*1024+1,64*1024] 1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对齐   freelist[184,208)
public:
		/*例子:bytes=7   alignNum=8
		*	alignNum-1=7		0000 0111
		*	~(alignNum-1)		1111 1000
		*	7+8-1=15			0000 1111
		*	&					0000 1000 = 8 = 对齐后所占大小
		*
		*	bytes=9		alignNum=8
		*	9+8-1=16			0001 0000
		*	&					0001 0000 = 16 = 对齐后所占大小
		*/
	//计算对齐后的bytes大小
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return (bytes + alignNum - 1) & ~(alignNum - 1);
	}
	//对齐大小计算
	static inline size_t RoundUp(size_t bytes)
	{
		assert(bytes >0);
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);

		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8*1024);
		}
		else
		{
			return _RoundUp(bytes, 1 << PAGE_SHIFT);//超过256Kb,按页大小对齐
		}
	}

	/*
	*	[1,8]	align_shift=3	1<<3=8
	*	((1+8-1)>>3)-1=0	0号桶
	*	...
	*	((8+8-1)>>3)-1=0	0号桶
	*	[9,16]	align_shift=3	1<<3=8
	*	((9+8-1)>>3)-1=1	1号桶
	*	...
	*	((16+8-1)>>3)-1=0	1号桶
	*	bytes=129	抛去bytes=128前的桶，只剩1bytes，再分配16字节对齐的0号桶,
		总号就是前128bytes桶号+当前16bytes的桶号
	*/
	//计算当前对齐大小对应的所在桶号
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}
	//计算映射在哪一个桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		//每个字节对齐数区间的最大链数（桶数）
		static int group[4] = { 16,56,56,56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group[1] + group[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group[2] + group[1] + group[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group[3] + group[2] + group[1] + group[0];
		}
		else {
			assert(false);
		}
		return -1;
	}
	// 一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}
	//计算一次向系统获取几个页
	// 单个对象 8byte
	 // ...
	 // 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;	//算出需要的总Byte大小
		npage >>= PAGE_SHIFT;		//总Byte大小/页大小=需要的页数
		if (npage == 0)
			npage = 1;
		return npage;
	}
};	

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux
#endif

struct Span
{
	PAGE_ID _pageId= 0;//大块内存起始页的页号
	size_t _n = 0;//页的数量,本质和PageCache中的SpanList数组（桶）下标一致，可以用来寻找挂接的桶位置

	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _objSize = 0;//切好的对象大小
	size_t _useCount = 0;//切好小块内存,分配个thread_cache的计数
	void* _freeList = nullptr;//切好小块内存的自由链表

	bool _isUse = false;//判断是否被使用
};
//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		Span* prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;
		pos->_prev = newSpan;
		newSpan->_next = pos;
	}
	Span* PopFront( )
	{
		Span* span = _head->_next;
		Erase(span);
		return span;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);//不能删带头结点

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
private:
	Span* _head;
public:
	std::mutex _mtx;
};

//堆上申请内存
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHIFT),
		MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
//堆上释放内存
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}